#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
/*
在由 2D 网格表示的校园里有 n 位工人（worker）和 m 辆自行车（bike），n <= m。所有工人和自行车的位置都用网格上的 2D 坐标表示。

我们为每一位工人分配一辆专属自行车，使每个工人与其分配到的自行车之间的曼哈顿距离最小化。

p1 和 p2 之间的曼哈顿距离为 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。

返回每个工人与分配到的自行车之间的曼哈顿距离的最小可能总和。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/campus-bikes-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注意自行车可能比工人多

示例 1：



输入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
输出：6
解释：
自行车 0 分配给工人 0，自行车 1 分配给工人 1 。分配得到的曼哈顿距离都是 3, 所以输出为 6 。
示例 2：



输入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
输出：4
解释：
先将自行车 0 分配给工人 0，再将自行车 1 分配给工人 1（或工人 2），自行车 2 给工人 2（或工人 1）。如此分配使得曼哈顿距离的总和为 4。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/campus-bikes-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution
{
public:
    int assignBikes(vector<vector<int>> &workers, vector<vector<int>> &bikes)
    {
        int nb = bikes.size();
        vector<int>dp(1 << 10,0x7f);
        dp[0] = 0;

        int cost[10][10];
        for (int i = 0; i < workers.size(); i++)
            for (int j = 0; j < bikes.size(); j++)
                cost[i][j] = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);

        for (int j = 0; j < workers.size(); j++)
        {
            for (int k = 0; k < 1 << nb; k++)
            {
                if (__builtin_popcount(k) == j)
                {
                    for (int i = 0; i < nb; i++)
                    {
                        if ((k & 1 << i) == 0)
                        {
                            dp[k | 1 << i] = min(dp[k | 1 << i], dp[k] + cost[j][i]);
                        }
                    }
                }
            }
        }
        int res = INT32_MAX;
        for (int i = 0; i < 1 << nb; i++)
        {
            if (__builtin_popcount(i) == workers.size())
                res = min(res, dp[i]);
        }
        return res;
    }
};